/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package mvp.algorithms.unions;

/**
 *
 * @author WORKSPOT2
 */
public class WeightedQuickUnion extends AbstractUnionAlgorithm
{

    private int sz[];

    public WeightedQuickUnion(int numberOfObjects)
    {
        super(numberOfObjects);
        this.sz = new int[numberOfObjects];
        for(int i=0; i < numberOfObjects; i++)
        {
            sz[i]++;
        }
    }

    @Override
    public void union(int p, int q)
    {
        int i = getRoot(p);
        int j = getRoot(q);
        if (i == j)
        {
            return;
        }
        if (sz[i] < sz[j])
        {
            id[i] = j;
            sz[j] += sz[i];
        }
        else
        {
            id[j] = i;
            sz[i] += sz[j];
        }
    }

    @Override
    public boolean isConnected(int p, int q)
    {
        return getRoot(p) == getRoot(q);
    }

    private int getRoot(int i)
    {
        while (i != id[i])
        {
            i = id[i];
        }
        return i;
    }
}
